package com.dushougudu;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class LeecodeDP {

    /**
     * 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
     * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额
     */
    @Test
    public void rob() {
        int[] nums = {2, 7, 9, 3, 1};
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        assert 12 == dp[nums.length - 1];
    }

    /**
     * 括号生成
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
     */
    @Test
    public void generateParenthesis() {
        int n = 2;
        List<String> ans = new ArrayList<String>();
        backtrackParenthesis(ans, new StringBuilder(), 0, 0, n);
        for (String s : ans) {
            System.out.println(s);
        }
    }

    public void backtrackParenthesis(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == 2 * max) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append("(");
            backtrackParenthesis(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (open > close) {
            cur.append(")");
            backtrackParenthesis(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

    /**
     * 爬楼梯
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
     */
    @Test
    public void climbStairs() {
        int n = 5;
        int first = 1;
        int second = 2;
        int result = 0;
        for (int i = 2; i < n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        assert result == 8;
    }

    /**
     * 最大子序和
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
     */
    @Test
    public void maxSubArray() {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int temp = 0;
        int ans = nums[0];
        for (int num : nums) {
            temp = Math.max(temp + num, num);
            ans = Math.max(ans, temp);
        }
        assert ans == 6;
    }


    /**
     * 三角形最小路径和
     * 给定一个三角形 triangle ，找出自顶向下的最小路径和。<br>每一步只能移动到下一行中相邻的结点上。
     * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
     * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1<br>
     */
    @Test
    public void minimumTotal() {
        int[][] triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
        for (int i = triangle.length - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].length; j++) {
                triangle[i][j] = Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];
            }
        }
        assert triangle[0][0] == 11;
    }

    /**
     * 最长公共子序列
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
     */
    @Test
    public void longestCommonSubsequence() {
        String text1 = "abcbdab";
        String text2 = "bdcaba";
        int x = text1.length();
        int y = text2.length();

        int dp[][] = new int[x + 1][y + 1];

        for (int i = 1; i <= x; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= y; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        for (int[] d1 : dp) {
            for (int d2 : d1) {
                System.out.print(d2 + ",");
            }
            System.out.println();
        }
        assert 4 == dp[x][y];
    }

    /**
     * 凑硬币
     * 给你 k 种⾯值的硬币，⾯值分别为 c1, c2 ... ck ，每种硬币的数量⽆限，再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个⾦额
     */
    @Test
    public void collectCoin() {

    }

}
